/*
* @Date: 2021/3/4
* @Author: XueChengwu <xuechengwu@erayt.com>
* @Copyright: 2015-2019 Erayt, Inc.
* @Description: If you have some questions, please contact: xuechengwu@erayt.com.
*/
function calcShannonEnt(dataSet){
  var numEntries = dataSet.length;
  var featNum = dataSet[0].length;
  var labelCounts = new Map();
  for(var i = 0;i < dataSet.length;i++){
    var label = dataSet[i][featNum - 1];
    if(labelCounts.containsKey(label)){
      labelCounts.put(label,labelCounts.get(label) + 1);
    }else{
      labelCounts.put(label,1);
    }
  }
  var shannonEnt = 0.0;
  var keys = labelCounts.keySet();
  for(var i = 0;i < keys.length;i++){
    var prob = labelCounts.get(keys[i])/numEntries;
    shannonEnt = shannonEnt - prob * Math.log(prob)/Math.log(2);
  }
  return shannonEnt;
}

function splitDataSet(dataSet,axis,value){
  var retDataSet = [];
  for(var i = 0;i < dataSet.length;i++){
    var featVec = [...dataSet[i]];
    if(featVec[axis] == value){
      featVec.splice(axis, 1);
      retDataSet.push(featVec);
    }
  }
  return retDataSet;
}

function chooseBestFeatureToSplit(dataSet){
  var numFeatures = dataSet[0].length - 1;
  var baseEntropy = calcShannonEnt(dataSet);
  var bestInfoGain = 0.0;
  var bestFeature = -1;
  for(var i = 0;i < numFeatures;i++){
    var featList = dataSet.map(vo => vo[i]);
    var uniqueVals = unique(featList);
    var newEntropy = 0.0;
    for(var j = 0;j < uniqueVals.length;j++){
      var subDataSet = splitDataSet(dataSet,i,uniqueVals[j]);
      var prob = subDataSet.length / dataSet.length;
      newEntropy = newEntropy +  prob * calcShannonEnt(subDataSet);
    }

    var infoGain = baseEntropy - newEntropy;
    if(infoGain > bestInfoGain){
      bestInfoGain = infoGain;
      bestFeature = i;
    }
  }
  return bestFeature;
}
function majorityCntCompare(v1,v2){
  if(v1 > v2){
    return true;
  }else{
    return false;
  }
}
function majorityCnt(classList){
  var classCount = new Map();
  for(var i = 0;i < classList.length;i++){
    var vote = classList[i];
    if(!classCount.containsKey(vote)){
      classCount.put(vote,0);
    }
    classCount.put(vote,classCount.get(vote) + 1);
  }
  return classCount.max()[0];

}

function unique(vector) {
  return [...new Set(vector)];
}

function createTree(dataSet,labels){
  var featNum = dataSet[0].length - 1;
  var classList = dataSet.map(vo => vo[featNum]);
  if(classList.count(classList[0]) == classList.length){
    return classList[0];
  }
  if(featNum == 0){
    return majorityCnt(classList)
  }
  var bestFeat = chooseBestFeatureToSplit(dataSet);
  var bestFeatLabel = labels[bestFeat]
  var myTree = new Map();
  myTree.put(bestFeatLabel,new Map());
  labels.splice(bestFeat,1);
  var featValues = dataSet.map(vo => vo[bestFeat]);
  var uniqueVals = unique(featValues);
  var tmp = new Map();
  for(var i = 0;i < uniqueVals.length;i++){
    var subLabels = [];
    for(var j = 0;j < labels.length;j++){
      subLabels.push(labels[j]);
    }
    tmp.put(uniqueVals[i],createTree(splitDataSet(dataSet,bestFeat,uniqueVals[i]),subLabels));

  }
  myTree.put(bestFeatLabel,tmp);
  return myTree
}
function find(v,value){
  for(var i = 0;i < v.length;i++){
    if(v[i] == value){
      return i;
    }
  }
  return -1;
}
function classify(inputTree,featLabels,testVec){
  var firstStr = inputTree.keySet()[0];
  var secondDict = inputTree.get(firstStr);
  var featIndex = find(featLabels,firstStr);
  var secondKeys = secondDict.keySet();
  var classLabel = -1;
  for(var i = 0;i < secondKeys.length;i++){
    if(testVec[featIndex] == secondKeys[i]){
      console.log(testVec[featIndex]);
      if(secondDict.get(secondKeys[i]) instanceof Map){
        classLabel = classify(secondDict.get(secondKeys[i]),featLabels,testVec);
      }else{
        classLabel = secondDict.get(secondKeys[i]);
      }
    }
  }
  return classLabel;
}
